public class O13 {
    public int movingCount(int m, int n, int k) {
        return dfs(m,n,0,0,new boolean[m][n],k);
    }
    int dfs(int m, int n, int i, int j, boolean[][] visit, int k){
        if (i>=m||j>=n||visit[i][j]||(i/10+i%10+j/10+j%10)>k)
            return 0;
        visit[i][j] = true;
        return dfs(m,n,i+1,j,visit,k)+dfs(m,n,i,j+1,visit,k)+1;
    }
}
